迷宫 [树，思维题]
迷宫 [树，思维题]
Wannafly Day 5 A
题目来源：comet OJ
分析
首先很明显，题目中给出的是一颗树。我们需要将所有的人移到根节点，并且一个节点同时刻只能有一个人。
我们先假设如果不会有人的位置发生冲突的话，那么花费的时间其实就等于深度最大的人所花费的时间。但实际情况是有可能会有两个人同时需要进入同一个父节点（发生冲突），所以其中一个需要为另一个让路。那么我们可以发现，深度相同的节点之间一定会早晚发生冲突。两个节点发生冲突的结果就是其中一个需要多花费一个时间节点，那么若是三个节点发生冲突呢？一个节点多花费一个时间节点，还有一个多花费两个时间节点。也就是说，对于深度相同的节点来说，若共有\(n\)个人，那么便需要比起一个人多花费\(n-1\)的时间将所有人走完。
那么，我们便可以系统地考虑一下这道题里的情况了。我们可以令深度更小的节点一定先到达根节点，这可以确保答案最小。然后我们每一层都有两个关键的性质：深度depth和人数n。然后我们用t[i]表示深度为i的人走完后所花费的时间。深度能够决定当前层的第一个人到达根节点的可能最小时间（实际并不一定是，因为可能深度更小的节点的人未走完），人数则表示该层共花费的时间。那么公式便如下：
\[ t[i] = max(t[ i - 1], depth - 1) + n - 1 \]
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include <iostream>
#include <algorithm>
#include <queue>
#define MAXN 100100
#define INF 0x3f3f3f3f
using namespace std;
int a[MAXN];
int dist[MAXN];
bool flag[MAXN];
int maxDepth = 0;
struct Node
{
struct Edge *edge;
int num, depth, max;
Node()
{
edge = NULL;
depth = num = 0;
max = INF;
}
}node[MAXN];
struct Edge
{
Node *from, *to;
Edge *next;
Edge()
{
from = to = NULL;
next = NULL;
}
Edge(Node *from, Node *to, Edge *next=NULL)
:from(from), to(to), next(from->edge) {}
};
int cnt[MAXN];
queue<Node *> q;
void build(Node *nd)
{
q.push(nd);
while (!q.empty())
{
Node *node = q.front();
q.pop();
for (Edge *e = node->edge; e; e = e->next)
{
if (e->to->depth == 0)
{
e->to->depth = node->depth + 1;
if (e->to->num==1)
cnt[e->to->depth] ++;
maxDepth = max(maxDepth, e->to->depth);
q.push(e->to);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1; i<=n; i++)
cin >> node[i].num;
for (int i = 1; i<n; i++)
{
int x, y;
cin >> x >> y;
node[x].edge = new Edge(&node[x], &node[y]);
node[y].edge = new Edge(&node[y], &node[x]);
}
node[1].depth = 1;
build(&node[1]);
if (node[1].num==1)
cnt[1] = 1;
int t = 0;
for (int i = 2; i<=maxDepth; i++)
if (i-1>t && cnt[i])
{
t = i - 2 + cnt[i];
}else if (i-1<=t && cnt[i])
{
t += cnt[i];
}
cout << t + cnt[1] << endl;
return 0;
}
|